package mo.offer_special;

import mo.common.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class L026 {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode tmp = head;
        List<ListNode> nodes = new ArrayList<>();
        while (tmp != null) {
            nodes.add(tmp);
            tmp = tmp.next;
        }

        int size = nodes.size();
        if (size <= 2) {
            return;
        }

        int times = (size - 1) / 2;
        ListNode current = head;
        while (times > 0) {
            ListNode tail = nodes.remove(nodes.size() - 1);
            ListNode tailHead = nodes.get(nodes.size()-1);
            tailHead.next = null;
            ListNode next = current.next;
            current.next = tail;
            tail.next = next;
            current = next;
            times--;
        }
    }

    public static void main(String[] args) {
        L026 test = new L026();
        ListNode head = ListNode.convertList2ListNode(Arrays.asList(1, 2, 3, 4));
        test.reorderList(head);
        System.out.println("complete");
    }


}
